OLIMPIADA NATIONALA DE INFORMATICA, SUCEAVA 1996
CLASA A XII-A
Ziua I 
Problema 1. (La ramp)
 	O firm de comercializare a calculatoarelor le depoziteaz pe o ramp liniar ....
REZOLVARE
	Deoarece momentele de depozitare sunt diferite si momentele livrarilor sunt independente de cele ale depozitarilor, se folosesc doi vectori de reperezentare a acestor momente, vectori de tip "permutare": 
d: (1 2 3 4) si l: (2 3 1 4) unde d_i reprezinta numarul de ordine la sosirea in depozit a produsului i, iar l_i numarul de ordine al produsului la plecarea din depozit pentru exemplul din problema.
Observatii:
O permutare a vectorului d implica o permutare echivalenta a vectorului l:
	asezarea pentru d (3 2 4 1) implica pentru vectorul l noua configuratie (1 3 4 2)
Orice permutare se obtine ca produs de transpozitii:
        asezarea (3 2 4 1) se obtine din (1 2 3 4) prin interschimbarile: (1 2), (1 3), (1 4), (2 3)
Daca asezarea produselor la depozitare se face optim (primul produs ocupa ultima pozitie, al doilea penultima, etc.) astfel incat nici un calculator depozitat sa nu treaca "peste" altul deja depozitat, orice noua transpozitie va conduce la cresterea, cel mult conservarea costului total.
        configuratia (4 3 2 1) pentru d conduce la costul total minim care se calculeaza cu formula
	cost=p*(inv(l_1)+inv(l_2)+...+inv(l_n)) unde inv(l_i) reprezinta numarul de calculatoare din fata lui l_i care au numar de ordine la livrare mai mare decat l_i (se livreaza mai tarziu, deci depasirea fiecaruia costa p)
In cazul nostru configuratia d (4 3 2 1)
                            l (4 1 3 2) are costul 1*(0+1+1+2)=4 care este minim.
Bineinteles, acelasi tip de rationament se poate face pentru fixarea configuratiei optime pentru l= (1 2 3 4) si calculul costului dupa numarul de "inversiuni mic-mare" din vectorul d
Pornind de la asezarea optima d: (n   n-1  ...   2    1)  l: (l_1 l_2  ... l_n-1 l_n),  unde l este o reasezare a vectorului l data de ordonarea vectorului d, se constata ca orice noua configuratie care conserva optimul este obtinuta prin transpozitii in l astfel incat produsul cu ordinea de livrare mai mare decat urmatorul comuta cu acesta.
Deci din configuratia optima d: ...  l: (4 1 3 2) se obtin configuratiile optime ... (1 4 3 2) si ...(4 1 2 3), iar din acestea se obtin alte configuratii  optime in construirea carora urmarim de fapt doar evolutia vectorului l: (1 3 4 2), (1 4 2 3), (1 3 2 4), (1 2 4 3) si (1 2 3 4).
Determinarea numarului de solutii optime presupune pornirea de la configuratia lui l data de ordonarea descrescatoare a elementelor lui d si generarea tuturor configuratiilor distincte obtinute prin interschimbari de tipul "mare-mic".
Se foloseste o formula de recurenta pentru calculul numarului de solutii reducand dimensiunea vectorului l:
nsol(l_1 l_2 ...l_i-1 l_i l_i+1... l_n)=suma(nsol(l_1 l_2 ... l_i-1 l_i+1 ... l_n)) dupa toate l_i care pot comuta cu l_i+1,.. l_n-1.
Astfel nsol(4 1 3 2)=nsol(1 3 2) + nsol(4 1 2) + nsol(4 1 3) deoarece atat 4 cat si 3 cat si 2 sunt sau pot ajunge pe ultima pozitie eliminandu-se astfel din sir.
Implementarea recursiva a formulei lucrand cu siruri de caractere (string sau z-string) este comoda insa mai lenta din cauza calculelor repetate ale aceleiasi valori.
In plus, se pot aduce o serie de optimizari formulei cum ar fi:
-daca l_1 este cel mai mare element din sir, atunci nsol(l_1..l_n)= n * nsol(l_2...l_n);
-daca l_n este cel mai mic element din sir, atunci nsol(l_1..l_n)= n * nsol(l_1...l_n-1).
